home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 98 / Skunkware 98.iso / src / shellutil / gzip-1.2.4.tar / gzip-1.2.4 / unlzh.c < prev    next >
C/C++ Source or Header  |  1993-08-13  |  9KB  |  402 lines
  1. /* unlzh.c -- decompress files in SCO compress -H (LZH) format.
  2.  * The code in this file is directly derived from the public domain 'ar002'
  3.  * written by Haruhiko Okumura.
  4.  */
  5.  
  6. #ifdef RCSID
  7. static char rcsid[] = "$Id: unlzh.c,v 1.2 1993/06/24 10:59:01 jloup Exp $";
  8. #endif
  9.  
  10. #include <stdio.h>
  11.  
  12. #include "tailor.h"
  13. #include "gzip.h"
  14. #include "lzw.h" /* just for consistency checking */
  15.  
  16. /* decode.c */
  17.  
  18. local unsigned  decode  OF((unsigned count, uch buffer[]));
  19. local void decode_start OF((void));
  20.  
  21. /* huf.c */
  22. local void huf_decode_start OF((void));
  23. local unsigned decode_c     OF((void));
  24. local unsigned decode_p     OF((void));
  25. local void read_pt_len      OF((int nn, int nbit, int i_special));
  26. local void read_c_len       OF((void));
  27.  
  28. /* io.c */
  29. local void fillbuf      OF((int n));
  30. local unsigned getbits  OF((int n));
  31. local void init_getbits OF((void));
  32.  
  33. /* maketbl.c */
  34.  
  35. local void make_table OF((int nchar, uch bitlen[],
  36.               int tablebits, ush table[]));
  37.  
  38.  
  39. #define DICBIT    13    /* 12(-lh4-) or 13(-lh5-) */
  40. #define DICSIZ ((unsigned) 1 << DICBIT)
  41.  
  42. #ifndef CHAR_BIT
  43. #  define CHAR_BIT 8
  44. #endif
  45.  
  46. #ifndef UCHAR_MAX
  47. #  define UCHAR_MAX 255
  48. #endif
  49.  
  50. #define BITBUFSIZ (CHAR_BIT * 2 * sizeof(char))
  51. /* Do not use CHAR_BIT * sizeof(bitbuf), does not work on machines
  52.  * for which short is not on 16 bits (Cray).
  53.  */
  54.  
  55. /* encode.c and decode.c */
  56.  
  57. #define MAXMATCH 256    /* formerly F (not more than UCHAR_MAX + 1) */
  58. #define THRESHOLD  3    /* choose optimal value */
  59.  
  60. /* huf.c */
  61.  
  62. #define NC (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD)
  63.     /* alphabet = {0, 1, 2, ..., NC - 1} */
  64. #define CBIT 9  /* $\lfloor \log_2 NC \rfloor + 1$ */
  65. #define CODE_BIT  16  /* codeword length */
  66.  
  67. #define NP (DICBIT + 1)
  68. #define NT (CODE_BIT + 3)
  69. #define PBIT 4  /* smallest integer such that (1U << PBIT) > NP */
  70. #define TBIT 5  /* smallest integer such that (1U << TBIT) > NT */
  71. #if NT > NP
  72. # define NPT NT
  73. #else
  74. # define NPT NP
  75. #endif
  76.  
  77. /* local ush left[2 * NC - 1]; */
  78. /* local ush right[2 * NC - 1]; */
  79. #define left  prev
  80. #define right head
  81. #if NC > (1<<(BITS-2))
  82.     error cannot overlay left+right and prev
  83. #endif
  84.  
  85. /* local uch c_len[NC]; */
  86. #define c_len outbuf
  87. #if NC > OUTBUFSIZ
  88.     error cannot overlay c_len and outbuf
  89. #endif
  90.  
  91. local uch pt_len[NPT];
  92. local unsigned blocksize;
  93. local ush pt_table[256];
  94.  
  95. /* local ush c_table[4096]; */
  96. #define c_table d_buf
  97. #if (DIST_BUFSIZE-1) < 4095
  98.     error cannot overlay c_table and d_buf
  99. #endif
  100.  
  101. /***********************************************************
  102.         io.c -- input/output
  103. ***********************************************************/
  104.  
  105. local ush       bitbuf;
  106. local unsigned  subbitbuf;
  107. local int       bitcount;
  108.  
  109. local void fillbuf(n)  /* Shift bitbuf n bits left, read n bits */
  110.     int n;
  111. {
  112.     bitbuf <<= n;
  113.     while (n > bitcount) {
  114.     bitbuf |= subbitbuf << (n -= bitcount);
  115.     subbitbuf = (unsigned)try_byte();
  116.     if ((int)subbitbuf == EOF) subbitbuf = 0;
  117.     bitcount = CHAR_BIT;
  118.     }
  119.     bitbuf |= subbitbuf >> (bitcount -= n);
  120. }
  121.  
  122. local unsigned getbits(n)
  123.     int n;
  124. {
  125.     unsigned x;
  126.  
  127.     x = bitbuf >> (BITBUFSIZ - n);  fillbuf(n);
  128.     return x;
  129. }
  130.  
  131. local void init_getbits()
  132. {
  133.     bitbuf = 0;  subbitbuf = 0;  bitcount = 0;
  134.     fillbuf(BITBUFSIZ);
  135. }
  136.  
  137. /***********************************************************
  138.     maketbl.c -- make table for decoding
  139. ***********************************************************/
  140.  
  141. local void make_table(nchar, bitlen, tablebits, table)
  142.     int nchar;
  143.     uch bitlen[];
  144.     int tablebits;
  145.     ush table[];
  146. {
  147.     ush count[17], weight[17], start[18], *p;
  148.     unsigned i, k, len, ch, jutbits, avail, nextcode, mask;
  149.  
  150.     for (i = 1; i <= 16; i++) count[i] = 0;
  151.     for (i = 0; i < (unsigned)nchar; i++) count[bitlen[i]]++;
  152.  
  153.     start[1] = 0;
  154.     for (i = 1; i <= 16; i++)
  155.     start[i + 1] = start[i] + (count[i] << (16 - i));
  156.     if ((start[17] & 0xffff) != 0)
  157.     error("Bad table\n");
  158.  
  159.     jutbits = 16 - tablebits;
  160.     for (i = 1; i <= (unsigned)tablebits; i++) {
  161.     start[i] >>= jutbits;
  162.     weight[i] = (unsigned) 1 << (tablebits - i);
  163.     }
  164.     while (i <= 16) {
  165.     weight[i] = (unsigned) 1 << (16 - i);
  166.     i++;
  167.     }
  168.  
  169.     i = start[tablebits + 1] >> jutbits;
  170.     if (i != 0) {
  171.     k = 1 << tablebits;
  172.     while (i != k) table[i++] = 0;
  173.     }
  174.  
  175.     avail = nchar;
  176.     mask = (unsigned) 1 << (15 - tablebits);
  177.     for (ch = 0; ch < (unsigned)nchar; ch++) {
  178.     if ((len = bitlen[ch]) == 0) continue;
  179.     nextcode = start[len] + weight[len];
  180.     if (len <= (unsigned)tablebits) {
  181.         for (i = start[len]; i < nextcode; i++) table[i] = ch;
  182.     } else {
  183.         k = start[len];
  184.         p = &table[k >> jutbits];
  185.         i = len - tablebits;
  186.         while (i != 0) {
  187.         if (*p == 0) {
  188.             right[avail] = left[avail] = 0;
  189.             *p = avail++;
  190.         }
  191.         if (k & mask) p = &right[*p];
  192.         else          p = &left[*p];
  193.         k <<= 1;  i--;
  194.         }
  195.         *p = ch;
  196.     }
  197.     start[len] = nextcode;
  198.     }
  199. }
  200.  
  201. /***********************************************************
  202.         huf.c -- static Huffman
  203. ***********************************************************/
  204.  
  205. local void read_pt_len(nn, nbit, i_special)
  206.     int nn;
  207.     int nbit;
  208.     int i_special;
  209. {
  210.     int i, c, n;
  211.     unsigned mask;
  212.  
  213.     n = getbits(nbit);
  214.     if (n == 0) {
  215.     c = getbits(nbit);
  216.     for (i = 0; i < nn; i++) pt_len[i] = 0;
  217.     for (i = 0; i < 256; i++) pt_table[i] = c;
  218.     } else {
  219.     i = 0;
  220.     while (i < n) {
  221.         c = bitbuf >> (BITBUFSIZ - 3);
  222.         if (c == 7) {
  223.         mask = (unsigned) 1 << (BITBUFSIZ - 1 - 3);
  224.         while (mask & bitbuf) {  mask >>= 1;  c++;  }
  225.         }
  226.         fillbuf((c < 7) ? 3 : c - 3);
  227.         pt_len[i++] = c;
  228.         if (i == i_special) {
  229.         c = getbits(2);
  230.         while (--c >= 0) pt_len[i++] = 0;
  231.         }
  232.     }
  233.     while (i < nn) pt_len[i++] = 0;
  234.     make_table(nn, pt_len, 8, pt_table);
  235.     }
  236. }
  237.  
  238. local void read_c_len()
  239. {
  240.     int i, c, n;
  241.     unsigned mask;
  242.  
  243.     n = getbits(CBIT);
  244.     if (n == 0) {
  245.     c = getbits(CBIT);
  246.     for (i = 0; i < NC; i++) c_len[i] = 0;
  247.     for (i = 0; i < 4096; i++) c_table[i] = c;
  248.     } else {
  249.     i = 0;
  250.     while (i < n) {
  251.         c = pt_table[bitbuf >> (BITBUFSIZ - 8)];
  252.         if (c >= NT) {
  253.         mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
  254.         do {
  255.             if (bitbuf & mask) c = right[c];
  256.             else               c = left [c];
  257.             mask >>= 1;
  258.         } while (c >= NT);
  259.         }
  260.         fillbuf((int) pt_len[c]);
  261.         if (c <= 2) {
  262.         if      (c == 0) c = 1;
  263.         else if (c == 1) c = getbits(4) + 3;
  264.         else             c = getbits(CBIT) + 20;
  265.         while (--c >= 0) c_len[i++] = 0;
  266.         } else c_len[i++] = c - 2;
  267.     }
  268.     while (i < NC) c_len[i++] = 0;
  269.     make_table(NC, c_len, 12, c_table);
  270.     }
  271. }
  272.  
  273. local unsigned decode_c()
  274. {
  275.     unsigned j, mask;
  276.  
  277.     if (blocksize == 0) {
  278.     blocksize = getbits(16);
  279.     if (blocksize == 0) {
  280.         return NC; /* end of file */
  281.     }
  282.     read_pt_len(NT, TBIT, 3);
  283.     read_c_len();
  284.     read_pt_len(NP, PBIT, -1);
  285.     }
  286.     blocksize--;
  287.     j = c_table[bitbuf >> (BITBUFSIZ - 12)];
  288.     if (j >= NC) {
  289.     mask = (unsigned) 1 << (BITBUFSIZ - 1 - 12);
  290.     do {
  291.         if (bitbuf & mask) j = right[j];
  292.         else               j = left [j];
  293.         mask >>= 1;
  294.     } while (j >= NC);
  295.     }
  296.     fillbuf((int) c_len[j]);
  297.     return j;
  298. }
  299.  
  300. local unsigned decode_p()
  301. {
  302.     unsigned j, mask;
  303.  
  304.     j = pt_table[bitbuf >> (BITBUFSIZ - 8)];
  305.     if (j >= NP) {
  306.     mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
  307.     do {
  308.         if (bitbuf & mask) j = right[j];
  309.         else               j = left [j];
  310.         mask >>= 1;
  311.     } while (j >= NP);
  312.     }
  313.     fillbuf((int) pt_len[j]);
  314.     if (j != 0) j = ((unsigned) 1 << (j - 1)) + getbits((int) (j - 1));
  315.     return j;
  316. }
  317.  
  318. local void huf_decode_start()
  319. {
  320.     init_getbits();  blocksize = 0;
  321. }
  322.  
  323. /***********************************************************
  324.         decode.c
  325. ***********************************************************/
  326.  
  327. local int j;    /* remaining bytes to copy */
  328. local int done; /* set at end of input */
  329.  
  330. local void decode_start()
  331. {
  332.     huf_decode_start();
  333.     j = 0;
  334.     done = 0;
  335. }
  336.  
  337. /* Decode the input and return the number of decoded bytes put in buffer
  338.  */
  339. local unsigned decode(count, buffer)
  340.     unsigned count;
  341.     uch buffer[];
  342.     /* The calling function must keep the number of
  343.        bytes to be processed.  This function decodes
  344.        either 'count' bytes or 'DICSIZ' bytes, whichever
  345.        is smaller, into the array 'buffer[]' of size
  346.        'DICSIZ' or more.
  347.        Call decode_start() once for each new file
  348.        before calling this function.
  349.      */
  350. {
  351.     local unsigned i;
  352.     unsigned r, c;
  353.  
  354.     r = 0;
  355.     while (--j >= 0) {
  356.     buffer[r] = buffer[i];
  357.     i = (i + 1) & (DICSIZ - 1);
  358.     if (++r == count) return r;
  359.     }
  360.     for ( ; ; ) {
  361.     c = decode_c();
  362.     if (c == NC) {
  363.         done = 1;
  364.         return r;
  365.     }
  366.     if (c <= UCHAR_MAX) {
  367.         buffer[r] = c;
  368.         if (++r == count) return r;
  369.     } else {
  370.         j = c - (UCHAR_MAX + 1 - THRESHOLD);
  371.         i = (r - decode_p() - 1) & (DICSIZ - 1);
  372.         while (--j >= 0) {
  373.         buffer[r] = buffer[i];
  374.         i = (i + 1) & (DICSIZ - 1);
  375.         if (++r == count) return r;
  376.         }
  377.     }
  378.     }
  379. }
  380.  
  381.  
  382. /* ===========================================================================
  383.  * Unlzh in to out. Return OK or ERROR.
  384.  */
  385. int unlzh(in, out)
  386.     int in;
  387.     int out;
  388. {
  389.     unsigned n;
  390.     ifd = in;
  391.     ofd = out;
  392.  
  393.     decode_start();
  394.     while (!done) {
  395.     n = decode((unsigned) DICSIZ, window);
  396.     if (!test && n > 0) {
  397.         write_buf(out, (char*)window, n);
  398.     }
  399.     }
  400.     return OK;
  401. }
  402.